Minimum add to make parentheses valid

Time: O(N); Space: O(1); medium

Given a string S of ‘(’ and ‘)’ parentheses, we add the minimum number of parentheses ( ‘(’ or ‘)’, and in any positions ) so that the resulting parentheses string is valid.

Formally, a parentheses string is valid if and only if: * It is the empty string, or * It can be written as AB (A concatenated with B), where A and B are valid strings, or * It can be written as (A), where A is a valid string.

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

Example 1:

Input: s = “())”

Output: 1

Example 2:

Input: s = “(((”

Output: 3

Example 3:

Input: s = “()”

Output: 0

Example 4:

Input: s = “()))((”

Output: 4

Constraints:

  1. S.length <= 1000

  2. S only consists of ‘(’ and ‘)’ characters.

1: Balance

Intuition and Algorithm

Keep track of the balance of the string: the number of ‘(’‘s minus the number of’)’’s. A string is valid if its balance is 0, plus every prefix has non-negative balance.

The above idea is common with matching brackets problems, but could be difficult to find if you haven’t seen it before.

Now, consider the balance of every prefix of S. If it is ever negative (say, -1), we must add a ‘(’ bracket. Also, if the balance of S is positive (say, +B), we must add B ‘)’ brackets at the end.

[3]:

class Solution1(object):
    """
    Time: O(N), where N is the length of S.
    Space: O(1).
    """
    def minAddToMakeValid(self, S):
        """
        :type S: str
        :rtype: int
        """
        add, bal, = 0, 0
        for c in S:
            bal += 1 if c == '(' else -1
            if bal == -1:
                add += 1
                bal += 1
        return add + bal

[4]:

sol = Solution1()
s = "())"
assert sol.minAddToMakeValid(s) == 1
s = "((("
assert sol.minAddToMakeValid(s) == 3
s = "()"
assert sol.minAddToMakeValid(s) == 0
s = "()))(("
assert sol.minAddToMakeValid(s) == 4